#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/19 10:41
# @USER    : Shengji He
# @File    : ValidPalindrome.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        """
        Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

        Note: For the purpose of this problem, we define empty string as valid palindrome.

        Example 1:
            Input: "A man, a plan, a canal: Panama"

            Output: true
        Example 2:
            Input: "race a car"

            Output: false

        :param s:
        :return:
        """
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if left < right:
                if s[left].lower() != s[right].lower():
                    return False
                left += 1
                right -= 1
        return True


if __name__ == '__main__':
    S = Solution()
    s = "A man, a plan, a canal: Panama"
    print(S.isPalindrome(s))
    print('done')
